Search results for "Grammatical evolution"
showing 10 items of 12 documents
Applications of Evolutionary Computation
2011
EvoCOMPLEX Contributions.- Coevolutionary Dynamics of Interacting Species.- Evolving Individual Behavior in a Multi-agent Traffic Simulator.- On Modeling and Evolutionary Optimization of Nonlinearly Coupled Pedestrian Interactions.- Revising the Trade-off between the Number of Agents and Agent Intelligence.- Sexual Recombination in Self-Organizing Interaction Networks.- Symbiogenesis as a Mechanism for Building Complex Adaptive Systems: A Review.- EvoGAMES Contributions.- Co-evolution of Optimal Agents for the Alternating Offers Bargaining Game.- Fuzzy Nash-Pareto Equilibrium: Concepts and Evolutionary Detection.- An Evolutionary Approach for Solving the Rubik's Cube Incorporating Exact Met…
On the Non-uniform Redundancy in Grammatical Evolution
2016
This paper investigates the redundancy of representation in grammatical evolution (GE) for binary trees. We analyze the entire GE solution space by creating all binary genotypes of predefined length and map them to phenotype trees, which are then characterized by their size, depth and shape. We find that the GE representation is strongly non-uniformly redundant. There are huge differences in the number of genotypes that encode one particular phenotype. Thus, it is difficult for GE to solve problems where the optimal tree solutions are underrepresented. In general, the GE mapping process is biased towards short tree structures, which implies high GE performance if the optimal solution requir…
Structural difficulty in grammatical evolution versus genetic programming
2013
Genetic programming (GP) has problems with structural difficulty as it is unable to search effectively for solutions requiring very full or very narrow trees. As a result of structural difficulty, GP has a bias towards narrow trees which means it searches effectively for solutions requiring narrow trees. This paper focuses on the structural difficulty of grammatical evolution (GE). In contrast to GP, GE works on variable-length binary strings and uses a grammar in Backus-Naur Form (BNF) to map linear genotypes to phenotype trees. The paper studies whether and how GE is affected by structural difficulty. For the analysis, we perform random walks through the search space and compare the struc…
On the Locality of Standard Search Operators in Grammatical Evolution
2014
Offspring should be similar to their parents and inherit their relevant properties. This general design principle of search operators in evolutionary algorithms is either known as locality or geometry of search operators, respectively. It takes a geometric perspective on search operators and suggests that the distance between an offspring and its parents should be less than or equal to the distance between both parents. This paper examines the locality of standard search operators used in grammatical evolution (GE) and genetic programming (GP) for binary tree problems. Both standard GE and GP search operators suffer from low locality since a substantial number of search steps result in an o…
On the Non-uniform Redundancy of Representations for Grammatical Evolution: The Influence of Grammars
2018
The representation used in grammatical evolution (GE) is non-uniformly redundant as some phenotypes are represented by more genotypes than others. This article studies how the non-uniform redundancy of the GE representation depends on various types of grammars. When constructing the phenotype tree from a genotype, the used grammar determines Bavg, the average branching factor. Bavg measures the expected number of non-terminals chosen when mapping one genotype codon to a phenotype tree node. First, the paper illustrates that the GE representation induces a bias towards small trees. This bias gets stronger with lower Bavg. For example, when using a grammar with Bavg = 0.5, 75% of all genotype…
Teaching GP to program like a human software developer
2019
Program synthesis is one of the relevant applications of GP with a strong impact on new fields such as genetic improvement. In order for synthesized code to be used in real-world software, the structure of the programs created by GP must be maintainable. We can teach GP how real-world software is built by learning the relevant properties of mined human-coded software - which can be easily accessed through repository hosting services such as GitHub. So combining program synthesis and repository mining is a logical step. In this paper, we analyze if GP can write programs with properties similar to code produced by human software developers. First, we compare the structure of functions generat…
Using knowledge of human-generated code to bias the search in program synthesis with grammatical evolution
2021
Recent studies show that program synthesis with GE produces code that has different structure compared to human-generated code, e.g., loops and conditions are hardly used. In this article, we extract knowledge from human-generated code to guide evolutionary search. We use a large code-corpus that was mined from the open software repository service GitHub and measure software metrics and properties describing the code-base. We use this knowledge to guide the search by incorporating a new selection scheme. Our new selection scheme favors programs that are structurally similar to the programs in the GitHub code-base. We find noticeable evidence that software metrics can help in guiding evoluti…
Challenges of Program Synthesis with Grammatical Evolution
2020
Program synthesis is an emerging research topic in the field of EC with the potential to improve real-world software development. Grammar-guided approaches like GE are suitable for program synthesis as they can express common programming languages with their required properties. This work uses common software metrics (lines of code, McCabe metric, size and depth of the abstract syntax tree) for an analysis of GE’s search behavior and the resulting problem structure. We find that GE is not able to solve program synthesis problems, where correct solutions have higher values of the McCabe metric (which means they require conditions or loops). Since small mutations of high-quality solutions str…
Representations for evolutionary algorithms
2015
Successful and efficient use of evolutionary algorithms (EA) depends on the choice of the genotype, the problem representation (mapping from genotype to phenotype) and on the choice of search operators that are applied to the genotypes. These choices cannot be made independently of each other. The question whether a certain representation leads to better performing EAs than an alternative representation can only be answered when the operators applied are taken into consideration. The reverse is also true: deciding between alternative operators is only meaningful for a given representation. In EA practice one can distinguish two complementary approaches. The first approach uses indirect repr…
High Locality Representations for Automated Programming
2011
We study the locality of the genotype-phenotype mapping used in grammatical evolution (GE). GE is a variant of genetic programming that can evolve complete programs in an arbitrary language using a variable-length binary string. In contrast to standard GP, which applies search operators directly to phenotypes, GE uses an additional mapping and applies search operators to binary genotypes. Therefore, there is a large semantic gap between genotypes (binary strings) and phenotypes (programs or expressions). The case study shows that the mapping used in GE has low locality leading to low performance of standard mutation operators. The study at hand is an example of how basic design principles o…